#include <stddef.h>
// 给定一个单链表 L 的头节点 head ，单链表 L 表示为：

// L0 → L1 → … → Ln - 1 → Ln
// 请将其重新排列后变为：

// L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
// 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

struct ListNode {
    int val;
    struct ListNode *next;
};
 
struct ListNode* reverseList(struct ListNode* head){//反转链表
    if(!head) return head;
    struct ListNode* n1,*n2,*n3; 
    n1=NULL;//n1=反转过后的尾结点NULL
    n2=head;
    n3=n2->next;
    while(n2)
    {
        n2->next=n1;
        n1=n2;
        n2=n3;
        if(n3)
            n3=n3->next;
    }
    return n1;
}


void reorderList(struct ListNode* head){
    if(head==NULL||head->next==NULL) return;
    struct ListNode* list1=head;
    struct ListNode* list2=head;
    while(list2&&list2->next)//取中间节点 中间节点是第一个链表的尾节点
    {
        list1=list1->next;
        list2=list2->next->next;
    }
    
    struct ListNode* newhead=list1->next;//第二个链表的头节点
    list1->next=NULL;
    newhead=reverseList(newhead);

    //把第二个链表插入第一个链表
    struct ListNode* cur1=head;
    struct ListNode* cur2=newhead;
    while(cur1!=NULL&&cur2!=NULL)
    {
        struct ListNode* q1=cur1->next;
        struct ListNode* q2=cur2->next;
        cur1->next=cur2;
        cur1=q1;
        cur2->next=cur1;
        cur2=q2;
    }
    
}